//
//  ViewController.swift
//  Chapter3LinkedList
//
//  Created by TRS-Mobile on 2021/8/31.
//

import UIKit

class ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        // Do any additional setup after loading the view.
    }

    @IBAction func testAction(_ sender: UIButton) {
        
        example(of: "LinkedList") {
            var list = LinkedList<String>()
            list.push("A")
            list.push("B")
            list.push("C")
            list.push("D")
            print(list)
        }

        example(of: "append") {
            var list = LinkedList<String>()
            list.append("a")
            list.append("b")
            list.append("c")
            list.append("d")
            print(list)
        }

        example(of: "insert") {
            var list = LinkedList<String>()
            list.append("a")
            list.append("b")
            list.append("c")
            list.append("d")
            print("Before inserting: \(list)")
            var middleNode = list.node(at: 1)!
            print(middleNode)
            for idx in 1...4 {
                middleNode = list.insert(String(describing: idx), after: middleNode)
            }
            print(list)
        }

        example(of: "pop") {
            var list = LinkedList<Int>()
            list.push(3)
            list.push(2)
            list.push(1)
            print("Before popping list: \(list)")
            let poppedValue = list.pop()
            print("After popping list: \(list)")
            print("Popped value: " + String(describing: poppedValue))
        }

        example(of: "removing the last node") {
            var list = LinkedList<Int>()
            list.push(3)
            list.push(2)
            list.push(1)
            print("Before removing last node: \(list)")
            let removedValue = list.removeLast()
            print("After removing last node: \(list)")
            print("Removed value: " + String(describing: removedValue))
        }

        example(of: "removing a node after a particular node") {
            var list = LinkedList<Int>()
            list.push(3)
            list.push(2)
            list.push(1)
            print("Before removing at particular index: \(list)")
            let index = 1
            let node = list.node(at: index - 1)!
            let removedValue = list.remove(after: node)
            print("After removing at index \(index): \(list)")
            print("Removed value: " + String(describing: removedValue))
        }

        example(of: "using collection") {
            var list = LinkedList<Int>()
            for i in 0...9 {
                list.append(i)
            }
            print("List: \(list)")
            print("First element: \(list[list.startIndex])")
            print("Array containing first 3 elements: \(Array(list.prefix(3)))")
            print("Array containing last 3 elements: \(Array(list.suffix(3)))")
            let sum = list.reduce(0, +)
            print("Sum of all values: \(sum)")
        }
        
        example(of: "linked list cow") {
            var list1 = LinkedList<Int>()
            list1.append(1)
            list1.append(2)
            list1.append(3)
//            print("List1 uniquely referenced:\(isKnownUniquelyReferenced(&list1[list1.startIndex]))")
            var list2 = list1
//            print("List1 uniquely referenced:\(isKnownUniquelyReferenced(&list1))")
            print("List1: \(list1)")
            print("List2: \(list2)")
            print("After appending 3 to list2")
            list2.append(3)
            print("List1: \(list1)")
            print("List2: \(list2)")
        }
    }
    
    @IBAction func stackTest(_ sender: UIButton) {
        example(of: "using a stack") {
            var stack = Stack<Int>()
            for i in 1...5 {
                stack.push(i)
            }
            print(stack)
            if let poppedElement = stack.pop() {
                print("Popped: \(poppedElement)")
            }
        }
        example(of: "initializing a stack from an array") {
            let array = ["A", "B", "C", "D", "E"]
            var stack = Stack(array)
            print(stack)
            print(stack.pop() ?? "")
        }
        
        example(of: "initializing a stack from an array literal") {
            var stack: Stack = [1.0, 2.0, 3.0, 4.0]
            print(stack)
            print(stack.pop() ?? "")
        }
    }
    
    @IBAction func queueAction(_ sender: UIButton) {
        example(of: "QueueArray") {
            var queue = QueueArray<String>()
            var p = queue.peek
            print(p ?? "")
            queue.enqueue("Ray")
            queue.enqueue("Brian")
            queue.enqueue("Eric")
            queue.dequeue()
            p = queue.peek
            print(p ?? "")
        }
        
        example(of: "QueueLinkedList") {
            var queue = QueueLinkedList<String>()
            var p = queue.peek
            print(p ?? "")
            queue.enqueue("Ray")
            queue.enqueue("Brian")
            queue.enqueue("Eric")
            print(p ?? "")
            queue.dequeue()
            p = queue.peek
            print(p ?? "")
        }
        
        example(of: "QueueRingBuffer") {
            var queue = QueueRingBuffer<String>(count: 10)
//            var p = queue.peek
//            print(p ?? "")
            for idx in 1...20 {
                if queue.isFull {
                    queue.dequeue()
                }
                queue.enqueue(String(describing: idx))
            }
//            queue.enqueue("Ray")
//            queue.enqueue("Brian")
//            queue.enqueue("Eric")
//            print(p ?? "")
//            queue.dequeue()
//            p = queue.peek
//            print(p ?? "")
        }
        example(of: "QueueStack") {
            var queue = QueueStack<String>()
            for idx in 1...20 {
                queue.enqueue(String(describing: idx))
                if idx % 3 == 0 {
                    queue.dequeue()
                    queue.dequeue()
                }
            }
        }
    }
    
    @IBAction func treeAction(_ sender: UIButton) {
        example(of: "creating a tree") {
            let beverages = TreeNode("beverages")
            let hot = TreeNode("Hot")
            let cold = TreeNode("cold")
            beverages.add(hot)
            beverages.add(cold)
        }
        
        example(of: "depth-first traversal") {
            let tree = makeBeverageTree()
            tree.forEachDepthFirst { print($0.value) }
        }
        example(of: "level-order traversal") {
            let tree = makeBeverageTree()
            tree.forEachLevelOrder { print($0.value) }
        }
        
        example(of: "searching for a node") {
            let tree = makeBeverageTree()
            if let re1 = tree.search("milk") {
                print("Found node: \(re1.value)")
            }
            if let re2 = tree.search("WKD Blue") {
                print("Found node: \(re2.value)")
            }else {
                print("Couldn't find WKD Blue")
            }
        }
        example(of: "tree diagram") {
            let tree = intBinaryTree()
            print(tree)
        }
        example(of: "in-order traversal") {
            let tree = intBinaryTree()
            tree.traverseInOrder { print($0) }
        }
        example(of: "pre-order traversal") {
            let tree = intBinaryTree()
            tree.traversePreOrder { print($0) }
        }
        example(of: "Post-order traversal") {
            let tree = intBinaryTree()
            tree.traversePostOrder { print($0) }
        }
        
        example(of: "building a BST") {
            var bst = BinarySearchTree<Int>()
            for i in 0..<5 {
                bst.insert(i)
            }
            print(bst)
        }
        print(aIntBinarySearchTree())
        example(of: "finding a node") {
            let bst = aIntBinarySearchTree()
            if bst.contains(5) {
                print("found !!!!!!!")
            }else {
                print("Not found")
            }
        }
        
        example(of: "removing a node") {
            var bst = aIntBinarySearchTree()
            print(bst)
            bst.remove(3)
            print(bst)
        }
    }
    @IBAction func AVLTreeAction(_ sender: UIButton) {
        example(of: "repeated insertions in sequence") {
            var tree = AVLTree<Int>()
            for i in 0..<15 {
                tree.insert(i)
            }
            print(tree)
        }
        
        example(of: "removing a value") {
            var tree = AVLTree<Int>()
            for i in 0..<15 {
                tree.insert(i)
            }
            print(tree)
            tree.remove(7)
            print(tree)
        }
    }
    
    @IBAction func triesAction(_ sender: UIButton) {
        example(of: "insert and contains") {
            let trie = Trie<String>()
            trie.insert("cute")
            if trie.contains("cute") {
                print("cute is in the trie")
            }
        }
        example(of: "remove") {
            let trie = Trie<String>()
            trie.insert("cut")
            trie.insert("cute")
            print("\n*** Before removing ***")
            assert(trie.contains("cut"))
            print("\"cut\" is in the trie")
            assert(trie.contains("cute"))
            print("\"cute\" is in the trie")
            print("\n*** After removing cut ***")
            trie.remove("cut")
            assert(!trie.contains("cut"))
            assert(trie.contains("cute"))
            print("\"cute\" is still in the trie")
        }
        
        example(of: "prefix matching") {
            let trie = Trie<String>()
            trie.insert("car")
            trie.insert("card")
            trie.insert("care")
            trie.insert("cared")
            trie.insert("cars")
            trie.insert("carbs")
            trie.insert("carapace")
            trie.insert("cargo")
            print("\nCollections starting with \"car\"")
            let prefixedWithCar = trie.collections(startingWith: "car")
            print(prefixedWithCar)
            print("\nCollections starting with \"care\"")
            let prefixedWithCare = trie.collections(startingWith: "care")
            print(prefixedWithCare)
            
        }
        
        example(of: "binarySearch") {
            let array = [1, 5, 15, 17, 19, 22, 24, 31, 105, 150]
            let search31 = array.firstIndex(of: 31)
            let binarySearch31 = array.binarySearch(for: 31)
            print("index(of:): \(String(describing: search31))")
            print("binarySearch(for:): \(String(describing: binarySearch31))")
        }
        
    }
    
    @IBAction func heapAction(_ sender: UIButton) {
        example(of: "Heap") {
            var heap = Heap(sort: >, elements: [1,12,3,4,1,6,8,7])
            while !heap.isEmpty {
                print(heap.remove()!)
            }
        }
        
        example(of: "PriorityQueue") {
            var priorityQueue = PriorityQueue(sort: >, elements: [1,12,3,4,1,6,8,7])
            while !priorityQueue.isEmpty {
                print(priorityQueue.dequeue()!)
            }
        }
    }
    
    @IBAction func sortAction(_ sender: UIButton) {
        example(of: "bubble sort") {
//            var array = [9, 4, 10, 3]
            var array = [1,12,3,4,1,6,8,7]
            print("Original: \(array)")
            bubbleSort(&array)
            print("Bubble sorted: \(array)")
        }
        example(of: "selection sort") {
//            var array = [9, 4, 10, 3]
            var array = [1,12,3,4,1,6,8,7]
            print("Original: \(array)")
            selectionSort(&array)
            print("sorted: \(array)")
        }
        example(of: "insertion sort") {
//            var array = [9, 4, 10, 3]
            var array = [1,12,3,4,1,6,8,7]
            print("Original: \(array)")
            insertionSort(&array)
            print("sorted: \(array)")
        }
        example(of: "merge sort") {
            let array = [1,12,3,4,1,6,8,7]
            print("Original: \(array)")
            let re = mergeSort(array)
            print("sorted: \(re)")
        }
        example(of: "radix sort") {
            var array = [112,7123,1322,34,421,132,426,3483]
            print("Original: \(array)")
            array.radixSort()
            print("sorted: \(array)")
        }
        
        example(of: "Heap sort") {
            let array = [112,7123,1322,34,421,132,426,3483]
            let heap = Heap(sort: >, elements: array)
            print("Original: \(array)")
//            print(heap.sorted())
            print("sorted: \(heap.sorted())")
        }
        
        example(of: "Quick naive sort") {
            let array = [112,7123,1322,34,421,132,426,3483]
            print("Original: \(array)")
            let re = quickSortNaive(array)
            print("sorted: \(re)")
        }
        
        example(of: "quickSortLomuto sort") {
            var array = [112,7123,1322,34,421,132,426,3483,1,12,3,4,1,6,8,7,12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
            print("Original: \(array)")
            quickSortLomuto(&array, low: 0, high: array.count - 1)
            print("sorted: \(array)")
        }
        
        example(of: "quickSortMedian sort") {
            var array = [112,7123,1322,34,421,132,426,3483,1,12,3,4,1,6,8,7,12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
            print("Original: \(array)")
            quickSortMedian(&array, low: 0, high: array.count - 1)
            print("sorted: \(array)")
        }
        
        example(of: "quickSortHoare sort") {
            var array = [112,7123,1322,34,421,132,426,3483,1,12,3,4,1,6,8,7,12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
            print("Original: \(array)")
            quickSortHoare(&array, low: 0, high: array.count - 1)
            print("sorted: \(array)")
        }
        example(of: "quickSortDutchFlag sort") {
            var array = [112,7123,1322,34,421,132,426,3483,1,12,3,4,1,6,8,7,12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
            print("Original: \(array)")
            quickSortDutchFlag(&array, low: 0, high: array.count - 1)
            print("sorted: \(array)")
        }
    }
    
    @IBAction func graphAction(_ sender: Any) {
//        let graph = AdjacencyList<String>()
        let graph = AdjacencyMatrix<String>()
        
        let singapore = graph.createVertex(data: "Singapore")
        let tokyo = graph.createVertex(data: "Tokyo")
        let hongKong = graph.createVertex(data: "Hong Kong")
        let detroit = graph.createVertex(data: "Detroit")
        let sanFrancisco = graph.createVertex(data: "San Francisco")
        let washingtonDC = graph.createVertex(data: "Washington DC")
        let austinTexas = graph.createVertex(data: "Austin Texas")
        let seattle = graph.createVertex(data: "Seattle")
        
        graph.add(.undirected, from: singapore, to: hongKong, weight: 300)
        graph.add(.undirected, from: singapore, to: tokyo, weight: 500)
        graph.add(.undirected, from: hongKong, to: tokyo, weight: 250)
        graph.add(.undirected, from: tokyo, to: detroit, weight: 450)
        graph.add(.undirected, from: tokyo, to: washingtonDC, weight: 300)
        graph.add(.undirected, from: hongKong, to: sanFrancisco, weight: 600)
        graph.add(.undirected, from: detroit, to: austinTexas, weight: 500)
        graph.add(.undirected, from: austinTexas, to: washingtonDC, weight: 292)
        graph.add(.undirected, from: sanFrancisco, to: washingtonDC, weight: 337)
        graph.add(.undirected, from: washingtonDC, to: seattle, weight: 277)
        graph.add(.undirected, from: sanFrancisco, to: seattle, weight: 218)
        graph.add(.undirected, from: austinTexas, to: sanFrancisco, weight: 247)
        
        example(of: "graph.description") {
            print(graph.description)
            
            print("San Francisco Outgoing Flights:")
            print("--------------------------------")
            for edge in graph.edges(from: sanFrancisco) {
                print("from: \(edge.source) to: \(edge.destination)")
            }
        }
        
        example(of: "breadthFirstSearch") {
            let vertices = graph.breadthFirstSearch(from: singapore)
            vertices.forEach {
                print($0)
            }
        }
        
        example(of: "depthFirstSearch") {
            let vertices = graph.depthFirstSearch(from: singapore)
            vertices.forEach {
                print($0)
            }
        }
        
        
    }
    
    @IBAction func dijkstraAction(_ sender: UIButton) {
        
        example(of: "dijkstra") {
            let graph = AdjacencyList<String>()

            let a = graph.createVertex(data: "A")
            let b = graph.createVertex(data: "B")
            let c = graph.createVertex(data: "C")
            let d = graph.createVertex(data: "D")
            let e = graph.createVertex(data: "E")
            let f = graph.createVertex(data: "F")
            let g = graph.createVertex(data: "G")
            let h = graph.createVertex(data: "H")

            graph.add(.directed, from: a, to: b, weight: 8)
            graph.add(.directed, from: a, to: f, weight: 9)
            graph.add(.directed, from: a, to: g, weight: 1)
            graph.add(.directed, from: b, to: f, weight: 3)
            graph.add(.directed, from: b, to: e, weight: 1)
            graph.add(.directed, from: f, to: a, weight: 2)
            graph.add(.directed, from: h, to: f, weight: 2)
            graph.add(.directed, from: h, to: g, weight: 5)
            graph.add(.directed, from: g, to: c, weight: 3)
            graph.add(.directed, from: c, to: e, weight: 1)
            graph.add(.directed, from: c, to: b, weight: 3)
            graph.add(.undirected, from: e, to: c, weight: 8)
            graph.add(.directed, from: e, to: b, weight: 1)
            graph.add(.directed, from: e, to: d, weight: 2)
            
            let dijkstra = Dijkstra(graph: graph)
            let pathsFromA = dijkstra.shortestPath(from: a) // 1
            let path = dijkstra.shortestPath(to: d, paths: pathsFromA) // 2
            for edge in path { // 3
                print("\(edge.source) --(\(edge.weight ?? 0.0))--> \(edge.destination)")
            }
        }
    }
    
    
    @IBAction func primAction(_ sender: UIButton) {
        
        example(of: "prim") {
            let graph = AdjacencyList<Int>()
            let one = graph.createVertex(data: 1)
            let two = graph.createVertex(data: 2)
            let three = graph.createVertex(data: 3)
            let four = graph.createVertex(data: 4)
            let five = graph.createVertex(data: 5)
            let six = graph.createVertex(data: 6)

            graph.add(.undirected, from: one, to: two, weight: 6)
            graph.add(.undirected, from: one, to: three, weight: 1)
            graph.add(.undirected, from: one, to: four, weight: 5)
            graph.add(.undirected, from: two, to: three, weight: 5)
            graph.add(.undirected, from: two, to: five, weight: 3)
            graph.add(.undirected, from: three, to: four, weight: 5)
            graph.add(.undirected, from: three, to: five, weight: 6)
            graph.add(.undirected, from: three, to: six, weight: 4)
            graph.add(.undirected, from: four, to: six, weight: 2)
            graph.add(.undirected, from: five, to: six, weight: 6)

            let (cost,mst) = Prim().produceMinimumSpanningTree(for: graph)
            print("cost: \(cost)")
            print("mst:")
            print(mst)
        }
    }
    
}

func makeBeverageTree() -> TreeNode<String> {
    let tree = TreeNode("Beverages")
    let hot = TreeNode("hot")
    let cold = TreeNode("cold")
    let tea = TreeNode("tea")
    let coffee = TreeNode("coffee")
    let chocolate = TreeNode("cocoa")
    let blackTea = TreeNode("black")
    let greenTea = TreeNode("green")
    let chaiTea = TreeNode("chai")
    let soda = TreeNode("soda")
    let milk = TreeNode("milk")
    let gingerAle = TreeNode("ginger ale")
    let bitterLemon = TreeNode("bitter lemon")
    tree.add(hot)
    tree.add(cold)
    hot.add(tea)
    hot.add(coffee)
    hot.add(chocolate)
    cold.add(soda)
    cold.add(milk)
    tea.add(blackTea)
    tea.add(greenTea)
    tea.add(chaiTea)
    soda.add(gingerAle)
    soda.add(bitterLemon)
    return tree
}

func intBinaryTree() -> BinaryNode<Int> {
    let zero = BinaryNode(value: 0)
    let one = BinaryNode(value: 1)
    let five = BinaryNode(value: 5)
    let seven = BinaryNode(value: 7)
    let eight = BinaryNode(value: 8)
    let nine = BinaryNode(value: 9)
    seven.leftChild = one
    one.leftChild = zero
    one.rightChild = five
    seven.rightChild = nine
    nine.leftChild = eight
    return seven
}

func aIntBinarySearchTree() -> BinarySearchTree<Int> {
    var bst = BinarySearchTree<Int>()
    bst.insert(3)
    bst.insert(1)
    bst.insert(4)
    bst.insert(0)
    bst.insert(2)
    bst.insert(5)
    return bst
}
